#pragma once
#include <iostream>
using namespace std;
namespace xzq
{
    enum Colour
    {
        BLACK,
        RED
    };
    template <class T>
    struct RBTreeNode
    {
        RBTreeNode<T> *_left;
        RBTreeNode<T> *_right;
        RBTreeNode<T> *_parent;
        T _data;
        Colour _col;
        RBTreeNode(const T &data)
            : _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED)
        {
        }
    };
    template <class T, class Ref, class Ptr>
    struct __TreeIterator
    {
        typedef RBTreeNode<T> Node;
        typedef __TreeIterator<T, Ref, Ptr> Self;
        Node *_node;
        __TreeIterator(Node *node)
            : _node(node)
        {
        }
        Ref operator*()
        {
            return _node->_data;
        }
        Ptr operator->()
        {
            return &_node->_data;
        }
        Self &operator++()
        {
            if (_node->_right)
            {
                Node *subLeft = _node->_right;
                while (subLeft->_left)
                {
                    subLeft = subLeft->_left;
                }
                _node = subLeft;
            }
            else
            {
                Node *cur = _node;
                Node *parent = cur->_parent;
                while (parent && cur == parent->_right)
                {
                    cur = cur->_parent;
                    parent = parent->_parent;
                }
                _node = parent;
            }
            return *this;
        }
        Self &operator--()
        {
            return *this;
        }
        bool operator!=(const Self &s)
        {
            return _node != s._node;
        }
        bool operator==(const Self &s)
        {
            return _node == s._node;
        }
    };
    template <class K, class T, class KOfT>
    struct RBTree
    {
        typedef RBTreeNode<T> Node;

    public:
        typedef __TreeIterator<T, T &, T *> iterator;
        typedef __TreeIterator<T, const T &, const T *> const_iterator;
        iterator begin()
        {
            Node *cur = _root;
            while (cur && cur->_left)
            {
                cur = cur->_left;
            }
            return iterator(cur);
        }
        iterator end()
        {
            return iterator(nullptr);
        }
        void RotateL(Node *parent)
        {
            Node *subR = parent->_right;
            Node *subRL = subR->_left;
            parent->_right = subRL;
            if (subRL)
                subRL->_parent = parent;
            subR->_left = parent;
            Node *ppNode = parent->_parent;
            parent->_parent = subR;
            if (_root == parent)
            {
                _root = subR;
                subR->_parent = nullptr;
            }
            else
            {
                if (ppNode->_left == parent)
                    ppNode->_left = subR;
                else
                    ppNode->_right = subR;
                subR->_parent = ppNode;
            }
        }
        void RotateR(Node *parent)
        {
            Node *subL = parent->_left;
            Node *subLR = subL->_right;
            parent->_left = subLR;
            if (subLR)
                subLR->_parent = parent;
            subL->_right = parent;
            Node *ppNode = parent->_parent;
            parent->_parent = subL;
            if (_root == parent)
            {
                _root = subL;
                subL->_parent = ppNode;
            }
            else
            {
                if (ppNode->_left == parent)
                    ppNode->_left = subL;
                else
                    ppNode->_right = subL;
                subL->_parent = ppNode;
            }
        }
        pair<iterator, bool> Insert(const T &data)
        {
            if (_root == NULL)
            {
                _root = new Node(data);
                _root->_col = BLACK;
                return make_pair(iterator(_root), true);
            }
            KOfT koft;
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (koft(cur->_data) < koft(data))
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (koft(cur->_data) > koft(data))
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return make_pair(iterator(cur), false);
                }
            }
            cur = new Node(data);
            Node *newnode = cur;
            if (koft(parent->_data) < koft(cur->_data))
            {
                parent->_right = cur;
                cur->_parent = parent;
            }
            else
            {
                parent->_left = cur;
                cur->_parent = parent;
            }
            cur->_col = RED;
            while (parent && parent->_col == RED)
            {
                Node *grandfather = parent->_parent;
                if (grandfather->_left == parent)
                {
                    Node *uncle = grandfather->_right;
                    if (uncle && uncle->_col == RED)
                    {
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (cur = parent->_right)
                        {
                            RotateL(parent);
                            swap(parent, cur);
                        }
                        RotateR(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        break;
                    }
                }
                else
                {
                    Node *uncle = grandfather->_left;
                    if (uncle && uncle->_col == RED)
                    {
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        cur = grandfather;
                        parent = cur->_parent;
                    }
                    else
                    {
                        if (cur == parent->_left)
                        {
                            RotateR(parent);
                            swap(parent, cur);
                        }
                        RotateL(grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                        break;
                    }
                }
            }
            _root->_col = BLACK;
            return make_pair(iterator(newnode), true);
        }
        iterator find(const T &data) // const K &key
        {
            KOfT koft;
            Node *cur = _root;
            while (cur)
            {
                if (koft(cur->_data) < koft(data))
                {
                    cur = cur->_right;
                }
                else if (koft(cur->_data) > koft(data))
                {
                    cur = cur->_left;
                }
                else
                {
                    return iterator(cur);
                }
            }
            return iterator(nullptr);
        }
        bool IsValidRBTree()
        {
            Node *pRoot = _root;
            // 空树也是红黑树
            if (nullptr == pRoot)
                return true;
            // 检测根节点是否满足情况
            if (BLACK != pRoot->_col)
            {
                cout << "违反红黑树性质二：根节点必须为黑色" << endl;
                return false;
            }
            // 获取任意一条路径中黑色节点的个数
            size_t blackCount = 0;
            Node *pCur = pRoot;
            while (pCur)
            {
                if (BLACK == pCur->_col)
                    blackCount++;
                pCur = pCur->_left;
            }
            // 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
            size_t k = 0;
            return _IsValidRBTree(pRoot, k, blackCount);
        }
        bool _IsValidRBTree(Node *pRoot, size_t k, const size_t blackCount)
        {
            // 走到null之后，判断k和black是否相等
            if (nullptr == pRoot)
            {
                if (k != blackCount)
                {
                    cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
                    return false;
                }
                return true;
            }
            // 统计黑色节点的个数
            if (BLACK == pRoot->_col)
                k++;
            // 检测当前节点与其双亲是否都为红色
            Node *pParent = pRoot->_parent;
            if (pParent && RED == pParent->_col && RED == pRoot->_col)
            {
                cout << "违反性质三：没有连在一起的红色节点" << endl;
                return false;
            }
            return _IsValidRBTree(pRoot->_left, k, blackCount) &&
                   _IsValidRBTree(pRoot->_right, k, blackCount);
        }
        void _InOrder(Node *root)
        {
            if (root == nullptr)
                return;
            _InOrder(root->_left);
            // cout << root->_kv.first << ":" << root->_kv.second << endl;
            _InOrder(root->_right);
        }
        void InOrder()
        {
            _InOrder(_root);
        }

    private:
        Node *_root = nullptr;
    };
}